package tests;

public class Keyongyu {
    public static void main(String[] args) {
        final int[] ARRAY = new int[]{-4, 2, 10, 9, 8, 7, 6};
        quickSort(ARRAY);
        int N = 3;
        System.out.println(ARRAY[N - 1]);
    }

    /**
     * 快速排序
     *
     * @param array
     */
    public static void quickSort(int[] array) {
        int len;
        if (array == null || (len = array.length) == 0 || len == 1) {
            return;
        }
        quickSortInner(array, 0, len - 1);
    }

    private static void quickSortInner(int[] array, int left, int right) {
        if (left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while (i != j) {
            while (array[j] >= base && i < j) {
                j--;
            }

            while (array[i] <= base && i < j) {
                i++;
            }

            //交换两个数在数组中的位置
            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // 将基准数放到中间的位置
        array[left] = array[i];
        array[i] = base;

        quickSortInner(array, left, i - 1);
        quickSortInner(array, i + 1, right);
    }
}